package top.humbleyuan.backtrack;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 20:18
 * @Des 单词拆分
 * @pro 循环dp待完善
 */
public class LeetCode_139 {
    // 记忆(即剪枝)回溯
    public static void main(String[] args) {
        String s = "catsandog";
        ArrayList<String> wordDict = new ArrayList<>();
        wordDict.add("cats");
        wordDict.add("dog");
        wordDict.add("sand");
        wordDict.add("and");
        wordDict.add("cat");

        HashSet<String> set = new HashSet<>(wordDict);
        Boolean[] memo = new Boolean[s.length()];

        // 回溯dfs
        Boolean res = dfs(s, 0, set, memo);
        System.out.println(res);
    }

    /**
     * memo记录从字符串中第i个开始之后的字符串是否满足条件
     * @param s
     * @param begin
     * @param cur
     * @param memo
     * @return
     */
    public static boolean dfs(String s,int begin, HashSet<String> dic, Boolean[] memo) {
        if(begin == s.length()) {
            memo[begin] = true;
            return true;
        }

        // 如果有记录直接从记录里找
        if(memo[begin] != null) {
            return memo[begin];
        }

        for (int end = begin + 1; end < s.length(); end++) {

            // 找到匹配前缀了，进行下一部分的递归
            if(dic.contains(s.substring(begin, end)) && dfs(s, end, dic, memo)) {
                memo[begin] = true;
                return true;
            }

        }

        memo[begin] = false;
        return false;
    }
}
